package recursive;

import beans.ListNode;

/**
 * @author pengfei.hpf
 * @date 2020/3/11
 * @verdion 1.0.0
 * 25. K 个一组翻转链表
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。
 *
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 *
 *
 * 示例：
 *
 * 给你这个链表：1->2->3->4->5
 *
 * 当 k = 2 时，应当返回: 2->1->4->3->5
 *
 * 当 k = 3 时，应当返回: 3->2->1->4->5
 *
 *
 *
 * 说明：
 *
 * 你的算法只能使用常数的额外空间。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 */
public class ReverseKGroup {
    public ListNode reverseKGroup(ListNode head, int k){
        if(head == null){
            return head;
        }
        ListNode dummy = new ListNode(-1);
        ListNode node = dummy;
        while(head != null){
            node.next = reverse(head, k);
            if(canReverse){
                node = head;
                head = head.next;
            } else {
                break;
            }
        }
        return dummy.next;
    }

    ListNode successor = null;
    boolean canReverse = false;

    private ListNode reverse(ListNode head, int n){
        if(head.next == null && n != 1){
            canReverse = false;
            return head;
        }
        if(n == 1){
            successor = head.next;
            canReverse = true;
            return head;
        }
        ListNode last = reverse(head.next, --n);
        if(canReverse){
            head.next.next = head;
            head.next = successor;
            return last;
        }
        return head;
    }
}
